47. Traits Class(Tag Structure)

STL
- container
- iterator
- algorithm
- utility
<template>으로 정의되어 있음
// utility의 iter 거리만큼 이동시키는 advance 템플릿
template <typename IterT, typename DistT>
void advance(IterT& iter, DistT d);
반복자(iterator)에 대하여 += 연산자는 정의되어 있지 않다.
(+= 임의 접근 반복자에만 정의되어 있음)

반복자 종류
- 입력 반복자(input iterator)
전진만 가능, 한 번에 한칸만 이동, 위치에서 읽기만 가능(한 번만 읽을 수 있음)
ex) istream_iterator

- 출력 반복자(output iterator)
전진만 가능, 한 번에 한칸만 이동, 위치에서 쓰기만 가능(한 번만 쓸 수 있음)
ex) ostream_iterator

- 순방향 반복자(forward iterator)
입/출력 반복자+위치에서 읽기/쓰기 가능(여러번 읽고 쓸 수 있음)
ex) STL에서는 제공하지 않지만, 단일 연결 리스트의 반복자

- 양방향 반복자(bidirectional iterator)
순방향 반복자+뒤로 이동 가능
ex) STL set, multiset, list, map, multimap 등의 반복자

- 임의 접근 반복자(random access iterator)
양방향 반복자+”반복자 산술 연산(iterator arithmetic”
상수 시간안에 임의의 거리만큼 앞뒤로 이동시키는 연산을 지원
ex) STL vector, deue, string 등의 반복자
C++ 표준 라이브러리에는 위의 다섯 개의 반복자 범주를 각각 식별하기 위해
“태그(tag) 구조체”를 정의해서 사용한다.
struct input_iterator_tag{};
struct output_iterator_tag{};
struct forward_iterator_tag: public input_iterator_tag{};
struct bidirectional_iterator_tag: public forward_iterator_tag{};
struct random_access_iterator_tag: public bidirectional_iterator_tag{};
최소 공통 분모(lowest-common-denominator) 전략
모든 반복자는 ++, — 연산자를 지원한다. 반복자를 루프문을 통해 반복적으로 증가시키거나 감소시키는 소스는
모든 반복자에 대하여서 가능하다.
(단, 임의 접근 반복자 입장에서는 상수 시간의 반복자 산술 연산을
  선형 시간이 반복문을 사용하였기에, 손해가 있다.)
template <typename IterT, typename DistT>
void advance(IterT& iter, DistT d){
if(/*iter가 임의 접근 반복자인 경우*/){
iter+=d;
} else {
if(d>=0){while(d--)++iter; }
else{ while(d++)--iter; }
}
}
위와 같이 iter가 임의 접근 반복자인지 조건문을 통해 검사하고,
이에 맞는 연산자를 선택해서 사용할 수 있다.
연산자의 정보를 전달받기 위해 특성정보(Traits)를 사용한다
특성정보는 컴파일 도중에 주어진 타입의 정보를 얻을 수 있게 해주는 객체

특성 정보 요구사항
- 기본 제공 타입과 사용자 정의 타입에서 모두 실행 가능해야 한다.
(특성 정보 기법을 포인터 등의 기본제공 타입에 적응가능해야 한다, 타입 내의 중첩된 정보는 구현 안됨)

따라서 특성 정보는 해당 클래스 외부에 존재해야 한다.
template <typename IterT>
struct iterator_traits;
반복자는 위와 같이 iterator_traits라는 이름의 구조체가 특성정보용 템플릿으로 선언되어 있다.

iterator_traits<IterT>에는
IterT 타입의 각각에 대해 iterator_category라는 이름으로 typedef 선언되어 있다.
(해당 태그 구조체에 대응)
template </*...*/>
class deque{
public:
class iterator{
public:
typedef random_access_iterator_tag iterator_category;
// ...
};
// ...
};
template </*...*/>
class list{
public:
class iterator{
public:
typedef bidirectional_iterator_tag iterator_category;
// ...
};
// ...
};
// iterator_traits
template <typename IterT>
struct iterator_traits{
typedef typename IterT::iterator_category iterator_category;
// ...
};
// 기본 제공 포인터 타입에 대한 부분 템플릿 특수화
template <typename IterT>
struct iterator_traits<IterT*>
{
typedef random_access_iterator_tag iterator_category;
// ...
};
- 타입 관련 정보를 확인
- 정보를 식별하기 위한 이름을 선택
- 타입 관련 정보를 담은 템플릿 및 템플릿의 특수화 버전을 제공
template <typename IterT, typename DistT>
void advance(IterT& iter, DistT d){
if(typeid(typename std::iterator_traits<IterT>::iterator_category)==typeid(std::random_access_iterator_tag))
// ...
}
위와 같이 구현해서 IterT의 특성 타입을 함수내에서 알 수 있다.
IterT 타입은 컴파일 시간에 파악되며, if문은 실행 도중에 평가된다.
(if문을 컴파일 시간에 구현함으로써, 실행 시간을 줄일 수 있으며 실행 코드의 크기도 줄일 수 있다.)

오버로딩을 이용해서 컴파일 타임에 선택하도록 유도할 수 있다.
template <typename IterT, typename DistT>
void doAdvance(IterT& iter, DistT d, std::random_access_iterator_tag){
iter+=d;
}
template <typename IterT, typename DistT>
void doAdvance(IterT& iter, DistT d, std::bidirectional_iterator_tag){
if(d>=0){ while(d--)++iter; }
else{ while(d++)--iter; }
}
template <typename IterT, typename DistT>
void doAdvance(IterT& iter, DistT d, std::input_iterator_tag){
if(d<0){
throw std::out_of_range("Negative distance");
} else {
while(d--)++iter;
}
}
// advance에서 doAdvance 오버로드를 호출해서 컴파일 타임에 비교 가능
template <typename IterT, typename DistT>
void advance(IterT& iter, DistT d){
doAdvance(iter, d, typename std::iterator_traits<IterT>::iterator_categroy);
}
forward_iterator_tag는 input_iterator_tag를 상속 받았기 때문에,
input_iterator_tag를 매개변수로 받는 doAdvance는 forward_iterator도 인자로 받을 수 있다.
C++에서 표준 라이브러리에서 다양한 반복자 관련 정보(특성정보)를 제공한다.
- value_type(char_traits)
- numeric_limits(최소값, 최대값을 담고 있음)
- is_fundamental<T>(T가 기본제공 타입인지를 리턴)
- is_base_of<T1, T2>(T1이 T2와 같거나 T1이 T2의 기본 클래스인지 리턴)
iterator_traits
// tag structure
// xutility.h
struct input_iterator_tag{
// ...
};
struct output_iterator_tag{
// ...
};
struct forward_iterator_tag: public input_iterator_tag, output_iterator_tag{
// ...
};
struct bidirectional_iterator_tag: public forwrad_iterator_tag{
// ...
};
struct random_access_iterator_tag: public bidirectional_iterator_tag{
// ...
};
// iterator class
template <class _Mylist>
class _List_iterator: public _List_const_iterator<_Mylist>{
public:
typedef _List_iterator<_Mylist> _Myiter;
typedef _List_const_iterator<_Myiter> _Mybase;
// iterator_category
typedef bidirectional_iterator_tag iterator_category; // iterator_traits
// ...
};
template <class _Ty, class _Ax=allocator<_Ty>>
class list: public _List_val<_Ty, _Ax>
{
public:
typedef _List_val<_Ty, _Ax> _Mybase;
// ...
typedef _List_const_iterator<_Mybase> const_iterator;
typedef _List_iterator<_Mybase> iterator; // list::iterator
// ...
};
// iterator_traits structure
template <class _Iter>
struct iterator_traits{
typedef typename _Iter::iterator_category iterator_category; // iterator_category
typedef typename _Iter::value_type value_type;
typedef typename _Iter::difference_type difference_type;
typedef difference_type distance_type; // retain
typedef typename _Iter::pointer pointer;
typedef typename _Iter::reference reference;
};
template <class _Ty> // 기본 포인터를 위한 특수화
struct iterator_traits<_Ty*>{
typedef random_access_iterator_tag iterator_category; // iterator_category(random_access_iterator_tag)
typedef _Ty value_type;
typedef ptrdiff_t differnecee_type;
typedef ptrdiff_t distance_type; // retain
typedef _Ty* pointer;
typedef _Ty& reference;
};
// Function overloading(비교를 위한)
template <class _InIt, class _Diff>
inline void _Advance(_Init& _Where, _Diff _Off, input_interator_tag){
// ...
}
template <class _FI, class _Diff>
inline void _Advance(_FI& Where, _Diff _Off, forward_iterator_tag){
// ...
}
template <class _BI, class _Diff>
inline void _Advance(_BI& _Where, _Diff _Off, bidirectional_iterator_tag){
// ...
}
template <class _RI, class _Diff>
inline void _Advance(_RI& _Where, _Diff _Off, random_access_iterator_tag){
// ...
}
char_trait
// <iosfwd>
template <class _Elem>
struct char_traits: public _Char_traits<_Elem, long>{
// ...
};
template <>
struct char_traits<wchar_t>{
// ...
};
template <>
struct char_traits<char>{
// ...
};
typedef basic_string<char, char_traits<char>, allocator<char>> string;
typedef basic_string<wchar_t, char_traits<wchar_t>, acllocator<wchar_t>> wstring;
#if _HAS_CPP0X
typedef basic_string<char16_t, char_traits<char16_t>, allocator<char16_t>> u16string;
typedef basic_string<char32_t, char_traits<char32_t>, allocator<char32_t>> u32string;
#endif // _HAS_CPP0X
컴파일 타임에 타입을 구분하기 위해 특성정보 클래스를 이용한다.
iterator_traits는 태그 구조체를 사용
char_traits는 완전 특수화를 통해 char/wchar_t 에 대하여 처리를 달리한다.